//数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。 
//
// 
//
// 示例 1： 
//
// 
//输入：n = 3
//输出：["((()))","(()())","(())()","()(())","()()()"]
// 
//
// 示例 2： 
//
// 
//输入：n = 1
//输出：["()"]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= n <= 8 
// 
// Related Topics 字符串 回溯算法 
// 👍 1839 👎 0

/**
 * @author DaHuangXiao
 */
package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;

public class GenerateParentheses {
    public static void main(String[] args) {
        Solution solution = new GenerateParentheses().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
        // 视为二叉树的遍历
        // 先定左括号，再定右括号
        // 只有当右括号数量大于左括号数量时才能添加左括号
    public List<String> generateParenthesis(int n) {
        List<String> ans = new ArrayList<>();
        StringBuilder stringBuilder = new StringBuilder();
        dfs(ans,stringBuilder,n,n);
        return ans;

    }
    public void dfs(List<String> ans, StringBuilder stringBuilder, int l, int r){
        if (l>r ||l<0 || r<0){
            return;
        }
        if (l==0 && r==0){
            ans.add(stringBuilder.toString());
            return;
        }


        stringBuilder.append('(');
        dfs(ans,stringBuilder,l-1,r);
        stringBuilder.deleteCharAt(stringBuilder.length()-1);
        stringBuilder.append(')');
        dfs(ans,stringBuilder,l,r-1);
        stringBuilder.deleteCharAt(stringBuilder.length()-1);

    }
}
//leetcode submit region end(Prohibit modification and deletion)

}